package LanQiaoCompetition.LanQiaoCompetition2;

public class Basic_27 {

    public static int n = 8;
    public static int checkerboard[][] = new int[n][n];
    public static int row[] = new int[n];
    public static int index = 0;
    public static int result = 0;

    //2n皇后问题  搜索算法
    public static void main(String args[]) {
        //初始化棋盘，0代表空闲
        for(int c =0;c<n;c++){
            for (int r=0;r<n;r++){
                checkerboard[c][r]=0;
            }
        }
        //初始化皇后的位置
        for(int i=0;i<n;i++){
            row[i] = 0;
        }
        //下棋 看是否需要回溯
        while (index>=0){
            Boolean boo = basic_27_chess();
            if(!boo){
                row[index]=0;
                index--;
                if(index<0){break;}
                checkerboard[index][row[index]]=0;
                row[index]++;
            }
            else if(index==n && boo){
                index--;
                if(index<0){
                    break;
                }
                checkerboard[index][row[index]]=0;
                row[index]++;
            }
        }
    }

    private static boolean basic_27_chess(){
        for(;row[index]<n;row[index]++){
            //判断是否可行
            if(basic_27_testChess()){
                checkerboard[index][row[index]]=1;
                index++;
                if(index==n){
                    basic_27_print();
                    return true;
                }
                break;
            }
        }
        //无路可走
        if(row[index]==n){
            System.out.println("回溯");
            return false;
        }
        return true;
    }

    private static boolean basic_27_testChess(){
        for(int i=0;i<index;i++){
            if(row[i]==row[index] || i+row[i]==index+row[index] || i-row[i]==index-row[index]){
                return false;
            }
        }
        return true;
    }

    private static void basic_27_print(){
        System.out.println(++result);
        for(int c=0;c<n;c++){
            for(int r=0;r<n;r++){
                System.out.print(checkerboard[c][r]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
